Initialization: Open [A, B], Closed [S]
Iteration 1: Open [A], Closed [S, B]
Iteration2: Open[E,F,A],Closed[S,B]
: Open [E, A], Closed [S, B, F]
Iteration3: Open[I,G,E,A],Closed[S,B,F]
: Open [I, E, A], Closed [S, B, F, G]
Hence the final solution path will be: S----> B----->F----> G
Time Complexity: The worst case time complexity of Greedy best first
search is O(b
m
).
Space Complexity: The worst case space complexity of Greedy best
first search is O(b
m
). Where, m is the maximum depth of the search
space.
Complete: Greedy best-first search is also incomplete, even if the
given state space is finite.
Optimal: Greedy best first search algorithm is not optimal.
2.) A* Search Algorithm:
A* search is the most commonly known form of best-first search. It
uses heuristic function h(n), and cost to reach the node n from the
start state g(n). It has combined features of UCS and greedy best-first
search, by which it solve the problem efficiently. A* search algorithm
finds the shortest path through the search space using the heuristic
function. This search algorithm expands less search tree and
provides optimal result faster.
A* algorithm is similar to UCS except that it uses g(n)+h(n) instead of
g(n).
In A* search algorithm, we use search heuristic as well as the cost to
reach the node.
Hence we can combine both costs as following, and this sum is called
as a fitness number.